package com.clstu.algrithm;

/**
 * 二分查找算法非递归版
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,3,4,6,8,9,10,15};
        System.out.println(binarySearch(arr,155));
    }

    //编写方法实现二分查找,返回下标,没找到返回-1(非递归),要求数组有序
    public  static int binarySearch(int[] arr,int findVal){
        //思路分析,while循环判断,大了往右边找,小了往左边找
        int mid;
        int left = 0;
        int right = arr.length;
        while (true){
            mid=left+(right-left)/2;
            //如果找到最后
            if(left >= right ){
                break;
            }
            //如果大于
            if(findVal>arr[mid]){
                left=mid+1;
            }else if(findVal<arr[mid]){
                //如果小于
                right = mid-1;
            }else {
                //如果找到
                return mid;
            }
        }
        //如果没有找到
        return -1;
    }
}
